package main

import (
	"sort"
	"fmt"
)

/**
标签：数组遍历
首先对数组进行排序，排序后固定一个数 nums[i],
再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R],
计算三个数的和 sum 判断是否满足为 0,满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环

nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sumsum == 00 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
当 sumsum == 00 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R--R−−
时间复杂度：O(n^2)O(n
2
 )，nn 为数组长度

作者：guanpengchn
链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */

func ThreeSum(nums []int) [][]int {
	sort.Ints(nums)
	fmt.Println(nums)
	n := len(nums)
	var res [][]int

	for i,_:=range nums{
		first:=i+1
		last:=n-1
		//fmt.Printf("%d:%d:%d\n",i,first,last)
		if first>n || last<=i{
			break
		}

		//右便的数都比他大，所以不用找了。
		if nums[i]>0{
			break
		}

		//如果不是第一个，那么如果他和之前找过的数字一样后面再找可能重复，或者已经没有了。所以直接break
		if i>0 && nums[i]==nums[i-1]{
			continue
		}

		for first<last{
			sum:=nums[i] + nums[first] + nums[last]
			//大于0，右指针左移动
			if sum >0 {
				last--
				continue
			}

			//小余0，左指针右移动
			if sum <0 {
				first++
				continue
			}

			//等于0，放入结果数组。并且判断下一个是否重复
			if sum ==0 {
				tmp:=[]int{nums[i],nums[first],nums[last]}
				res = append(res,tmp)

				//判断下一个字母是否和当前满足条件的一样，如果for改成if会找不出三连排的重复数字
				for first<last && nums[first+1]==nums[first]{
					first++
				}
				for first<last && nums[last-1]==nums[last]{
					last--
				}


				last--
				first++
				continue
			}


		}

	}


	//m:=make(map[int][]int)

	//n:=len(nums)
	//for i,v:=range nums{
	//	for j:=i+1;j<n;j++{
	//		//m[v+nums[j]]=make([]int,2)
	//		m[v+nums[j]]=[]int{i,j}
	//		//fmt.Println(i,v,nums[j])
	//
	//	}
	//}
	//for i,v:=range nums{
	//	find:=0-v
	//	if _,ok:=m[find];ok{
	//		if i!=m[find][0] && i!=m[find][1]{
	//			tmp:=[]int{v,nums[m[find][0]],nums[m[find][1]]}
	//			//fmt.Println(v, nums[m[find][0]], nums[m[find][1]])
	//			//fmt.Println(tmp)
	//			res = append(res,tmp)
	//		}
	//	}
	//	//fmt.Println(find)
	//}
	////去重 todo
	////{-1, 0, 1, 2, -1, -4}
	////[[-1,-1,2],[-1,0,1]]
	return res
}
